package leetcode_500;

/**
 *@author 周杨
 *SplitArrayLargestSum_410_  给定一个正整数N 求数组被划分成n个连续数组 他们中间最大值的最小值
 *describe:用二分搜索 搜索区域  AC 100%
 *see:https://blog.csdn.net/u014688145/article/details/69525838
 *2018年7月20日 下午5:33:37
 */
public class SplitArrayLargestSum_410_ {
	
	public static void main(String[] args) {
		SplitArrayLargestSum_410_ test=new SplitArrayLargestSum_410_();
		test.splitArray(new int[] {7,2,5,10,8}, 2);
	}
	public int splitArray(int[] nums, int m) {
        long sum = 0;
        int max = 0;
        for(int num: nums){
            max = Math.max(max, num);
            sum += num;
        }
        return (int)binary(nums, m, sum, max);
    }

    /**
     * describe:二分搜索值区域  为什么最终值一定是合法值 因为解一定在这个解空间内 不断压缩这个空间 最终值就是答案
     * 2018年7月21日 上午11:41:48
     */
    private long binary(int[] nums, int m, long high, long low){
        long mid = 0;
        while(low < high){
            mid = (high + low)/2;
            if(valid(nums, m, mid)){//表明此mid太高 没有太多连续数组能达到要求
                high = mid;
            }else{//表明这个mid刚好符合或者多于这个最终值 尽量靠近最终值
                low = mid + 1;
            }
        }
        return high;//因为low可能超越了high
    }

    private boolean valid(int[] nums, int m, long max){
        int cur = 0;
        int count = 1;
        for(int num: nums){
            cur += num;
            if(cur > max){
                cur = num;
                count++;
                if(count > m){
                    return false;
                }
            }
        }
        return true;
    }
}
